#define _CRT_SECURE_NO_WARNINGS 1
//交换
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//三数取中
int GetMidi(int* a, int left, int right)
{
	//mid是随机的left到right中的一个值
	int mid = left + rand() % (right - left);

	// 比较三个元素：left, mid, right
	// 首先比较left和mid
	if (a[left] < a[mid])
	{
		// 如果left < mid，再比较mid和right
		if (a[mid] < a[right])
		{
			// 如果left < mid < right，则mid是中间值
			return mid;
		}
		else if (a[left] > a[right])  // 如果left > right，则mid是最大值
		{
			// 在这种情况下，left是中间值
			return left;
		}
		else
		{
			// 如果left < right，则right是中间值
			return right;
		}
	}
	else // 如果a[left] > a[mid]
	{
		// 比较mid和right
		if (a[mid] > a[right])
		{
			// 如果mid > right，则mid是中间值
			return mid;
		}
		else if (a[left] < a[right]) // 如果left < right，则mid是最小值
		{
			// 在这种情况下，left是中间值
			return left;
		}
		else
		{
			// 如果left > right，则right是中间值
			return right;
		}
	}
}
//三路划分
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int begin = left;
	int end = right;

	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int cur = left + 1;
	int key = a[begin];

	while (cur <= right)
	{
		//1.cur的值和tmp的相等的时候就直接cur++：
		if (a[cur] == key)
		{
			cur++;
		}
		//2.cur的值比tmp的值小的时候就进行left和cur的交换并且++两个：
		else if (a[cur] < key)
		{
			Swap(&a[cur], &a[left]);
			cur++;
			left++;
		}
		//3.cur的值比tmp的值大的时候
		//就进行right和cur的交换并且--一个right
		//不++cur是因为我们不知道交换来的数值具体和他mp的大小关系：
		else if (a[cur] > key)
		{
			Swap(&a[cur], &a[right]);
			right--;
		}
	}

	//结束循环之后,递归进入左右部分的三路划分

	QuickSort(a, begin, left - 1);
	QuickSort(a, right + 1, end);
}

int* sortArray(int* nums, int numsSize, int* returnSize) {

	srand(time(0));

	QuickSort(nums, 0, numsSize - 1);

	*returnSize = numsSize;

	return nums;
}